package day5;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class ch2 {

    //102
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> l = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode n = queue.poll();
                l.add(n.val);
                if(n.left!=null) queue.offer(n.left);
                if(n.right!=null) queue.offer(n.right);
            }
            list.add(l);
        }

        return list;
    }

    //108
    public TreeNode sortedArrayToBST(int[] nums) {
        return fun1(0,nums.length-1,nums);
    }

    public TreeNode fun1(int left,int right,int[] nums){
        if(left>right){
            return null;
        }
        int mid = (left+right)/2;
        TreeNode node = new TreeNode(mid);
        TreeNode l = fun1(left,mid-1,nums);
        TreeNode r = fun1(mid+1,right,nums);

        node.left = l;
        node.right = r;

        return node;
    }

    //98
    public boolean isValidBST(TreeNode root) {

        return fun2(root,Integer.MIN_VALUE,Integer.MAX_VALUE);
    }

    public boolean fun2(TreeNode node,int min,int max){

        if(node==null) return true;
        if(node.val<min&&node.val>max) return false;
        if(node.left!=null && node.val<=node.left.val) return false;
        if(node.right!=null && node.val>=node.right.val) return false;
        return fun2(node.left,min,node.val-1) && fun2(node.right,node.val+1,max);

    }

    //230
    public int kthSmallest(TreeNode root, int k) {

        List<Integer> list = new ArrayList<>();
        fun3(list,root);

        return list.get(k-1);


    }

    public void fun3(List<Integer> list,TreeNode node){
        if(node==null) return;
        fun3(list,node.left);
        list.add(node.val);
        fun3(list,node.right);

    }

    //114
    public void flatten(TreeNode root) {

    }






}
